Soit \(F_n\) le nombre de points fixes d'une permutation uniforme aléatoire de taille \(n\) \(S_n\)
Montrer que pour chaque \(n\), on a : $$E(F_n)=1\quad\text{ et }\quad\operatorname{Var}(F_n)=1$$

Écrire \(F_n\) comme la somme de variables aléatoires simples
Écrivons \(F_n\) sous la forme \(F_n=\sum^n_{i=1}X_i\), avec $$X_i=\begin{cases}1&\text{si}\quad S_n(i)=i\\ 0&\text{sinon.}&\end{cases}$$

On peut alors appliquer la linéarité de l'espérance et calculer les espérances unes à unes
Les \(X_i\) ne sont pas indépendantes, mais on a par la linéarité de l'espérance : $$E(F_n)=E(X_1+\dots+X_n)=E(X_1)+\dots+E(X_n)$$

Calculer l'espérance via formule d'équiprobabilité
Maintenant, $$P(X_i=1)=P(S_n(i)=i)=\frac{\operatorname{Card}\{\text{permutations }s\text{ de taille }n\text{ avec }s(i)=i\}}{\operatorname{Card}\{\text{permutations de taille }n\}}=\frac{(n-1)!}{n!}=\frac1n$$

Sommer pour avoir l'espérance de la grosse variable
On a donc : $$E(F_n)=\sum^n_{i=1}E(X_i)=\frac nn=1$$

Formule de la variance via addition
Pour calculer la variance, nous allons utiliser la formule : $$\operatorname{Var}\left(\sum^n_{i=1}X_i\right)=\sum_i\operatorname{Var}(X_i)+\sum_{i\ne j}\operatorname{Cov}(X_i,X_j)=n\operatorname{Var}(X_1)+n(n-1)\operatorname{Cov}(X_1,X_2)$$

Calculer la covariance
Par les calculs précédents, on a : $$E(X_1)=\frac1n\quad\text{ et }\quad\operatorname{Var}(X_1)=\frac1n\left(1-\frac1n\right)$$
On peut donc calculer $$E(X_1X_2)=P(X_1X_2=1)=P(X_1=1,X_2=1)=\frac{(n-2)!}{n!}=\frac1{n(n-1)}$$ d'où \(\operatorname{Cov}(X_1,X_2)=\frac1{n(n-1)}-\frac1{n^2}\)

Finir le calcul de la variance

Enfin, $$\operatorname{Var}(F_n)=1-\frac1n+n(n-1)\frac1{n^2(n-1)}=1$$

Toute permutation \(\sigma\) se décompose de façon unique en composés de cycles à supports disjoints
De plus, ce composé est commutatif

Initialisation triviale
Existence : on procède par récurrence forte
Initialisation : si \(n=1\), alors la seule permutation de \(\mathfrak S_1\) est l'identité, qui est un cycle de longueur \(1\)

Initialisation de l'hérédité : images successives
Hérédité : on suppose que le résultat est vérifié pour tout \(k\leqslant n\). Soit \(\sigma\) une permutation de \(\mathfrak S_{n+1}\). Soit \(E\) un ensemble de cardinal \(n+1\) et soit \(a\in E\)
On étudie les images successives de \(a\) par \(\sigma\) (l'orbite de \(a\) par \(\sigma\)) :
$$a,\sigma(a),\sigma^2(a),\dots,\sigma^{p-1}(a)$$
où \(p\) est le plus petit entier tel que l'in retombe sur un élément qu'on avait déjà obtenu avant : il existe \(q\in[\![0,p-1]\!]\) tel que \(\sigma^p(a)=\sigma^q(a)\)

Alors on peut revenir en arrière \(\to\) les antécédents sont les mêmes
Si \(q\ne0\), alors, par injectivité de \(\sigma\) : $$\sigma(\sigma^{p-1}(a))=\sigma(\sigma^{q-1}(a))\implies \sigma^{p-1}(a)=\sigma^{q-1}(a)$$

Contradiction \(\to\) on a démontré l'existence d'un cycle
Cela contredit le fait que \(p\) est le plus petit entier possible
Ainsi, on a démontré que les images successives de \(a\) (l'orbite de \(a\)) sont $$a,\sigma(a),\sigma^2(a),\dots,\sigma^{p-1}(a)$$ où ces éléments sont distincts deux à deux, et \(\sigma^p(a)=a\)

Notations
Posons \(E_1=\{a,\sigma(a),\dots,\sigma^{p-1}(a)\}\), \(E_2=E\backslash E_1\) et \(c_1=(a\,\sigma(a)\,\dots\,\sigma^{p-1}(a))\)
Si \(x\in E_1\), alors \(\sigma(x)=c_1(x)\)

Il nous faut étudier le cas où on n'a pas fini : restriction de \(\sigma\) à \(E_2\)

1. Si \(E_1=E\), on a fini
2. Sinon, on sait que \(1\leqslant\operatorname{Card}(E_2)\leqslant n\) et on considère \(\sigma^\prime\) la restriction de \(\sigma\) à \(E_2\)

\(\sigma^\prime\) est une permutation \(\to\) hypothèse de récurrence
\(\sigma^\prime\) est une permutation de \(E_2\) car \(\sigma^\prime\) est injective et \(\sigma^\prime(E_2)\subset E_2\) (sinon, il serait dans \(E_1\) et c'est impossible)
Par hypothèse de récurrence, on peut donc décomposer \(\sigma^\prime\) comme un produit de cycles disjoints \(\sigma^\prime=c_2\circ\dots\circ c_k\)
Finalement, on a : $$\sigma=c_1\circ c_2\circ\dots\circ c_k$$

Unicité : lemme
Pour montrer l'unicité, nous allons utiliser le lemme "un cycle est totalement déterminé par l'orbite d'un des éléments de son support (pour \(x\) dans les supports de \(c\) et \(c^\prime\), \(\forall k\geqslant0,c^k(x)=c^{\prime k}(x)\implies c=c^\prime\))"
En effet, $$\begin{align} c&=(x\quad c(x)\quad c^2(x)\quad \dots\quad c^{p-1}(x))\\ c^\prime&=(x\quad c^\prime(x)\quad c^{\prime2}(x)\quad\dots\quad c^{q-1}(x))\end{align}$$
La démonstration du lemme est immédiate

Supposer qu'il y a deux décompositions
Soit \(\sigma\) une permutation de \(E=\{1,\dots,n\}\) et supposons qu'on ait deux décompositions en cycles à supports disjoints $$\sigma=c_1\circ\dots\circ c_\ell\quad\text{ et }\quad\sigma=c^\prime_1\circ\dots\circ c^\prime_m$$

Réorganiser \(\to\) premier cycle identique
1

Itérer

On peut itérer sur chaque cycle et c'est bon
1

Quitte à réordonner les cycles, on peut supposer que \(1\in\operatorname{supp}(c_1)\cap\operatorname{supp}(c^\prime_1)\)
Alors, puisque pour tout \(k\geqslant0\), $$c_1^k(1)=c^{\prime k}_1(1)=\sigma^k(1)$$, on a \(c_1=c^\prime_1\)

Soit \(C_n\) le nombre de cycles disjoints d'une permutation aléatoire uniforme de taille \(n\) \(S_n\)
Montrer que quand \(n\to+\infty\), on a : $$E(C_n)\underset{+\infty}\sim\ln(n)$$

Décomposer la variable cherchée en une somme de variables plus simples
Supposons que \(S_n\) soit le résultat de l'algorithme du restaurant chinois
Lors du processus du restaurant chinois, un nouveau cycle se créé quand un client s'assoit à une nouvelle table : $$C_n=\sum^n_{i=1}Z_i\quad\text{ avec }\quad Z_i=\begin{cases}1&\text{si}\quad\text{ le client }i\text{ s}^\prime\text{assoit à une nouvelle table}\\ 0&\text{sinon.}&\end{cases}$$

Espérances des variables aléatoires simples
Le client \(i\) s'assoit à une nouvelle table avec la probabilité \(\frac1i\)
Donc \(E(Z_i)=\frac1i\)

Espérance de la grosse variable via linéarité de la somme
On a donc : $$E(C_n)=E\left(\sum^n_{i=1}Z_i\right)=\sum^n_{i=1}\frac1i$$

Utiliser l'équivalence de la série harmonique

On a donc $$E(C_n)=\sum^n_{i=1}\frac1i\underset{+\infty}\sim\ln(n)$$